Conventionally, as a technique for performing computation including multiplication and addition while ensuring correctness of a computation result, in a state of concealing data, three-party secure function evaluation of Non-patent literature 1 exists. This is a protocol for bringing about a result of an arithmetic/logical operation by cooperative computation by three parties (three computation subjects) without restoring a shared input value. In the three-party secure function evaluation protocol, data is treated as a natural number smaller than a certain determined prime number p. When data is to be concealed, and the data is indicated by a, a is shared into three such that the following condition is satisfied.a=a0+a1+a2 mod p 
Actually, random number a1 and a2 are generated, and a0=a−a1−a2 is obtained. Then, (a0,a1), (a1,a2) and (a2,a0) are transmitted to three parties X, Y and Z, respectively. Then, though none of X, Y and Z has information about a because a1 and a2 are random numbers, a can be restored if any two parties gather.
Since concealment is additive sharing, the same result is obtained irrespective of whether the shared values are restored after being added or added after being restored, due to commutativity of the concealment. That is, an addition and a constant multiplication can be performed without communication in a shared state. Further, a multiplication is also possible though communication and random number generation are required. Therefore, it is possible to configure a logical circuit and execute any computation. A specific example of the three-party secure function evaluation will be shown below. In the three-party secure function evaluation protocol, a computation result is a remainder of division by p. However, description of “mod p” will be omitted below for simplification of description.
(1) Restoration of Secret Data a Shared to X, Y and Z
X transmits a0 to Y, and transmits a1 to Z. Y transmits a1 to Z, and transmits a2 to X. Z transmits a2 to X and transmits a0 to Y.
If a2 received from Y and a2 received from Z correspond to each other, X computes a0+a1+a2 to restore a. If a0 received from X and a0 received from Z correspond to each other, Y computes a0+a1+a2 to restore a. If a1 received from X and a1 received from Y correspond to each other, Z computes a0+a1+a2 to restore a.
(2) Secret Computation of c=a+b
It is assumed that data b is also concealed by (b0,b1), (b1,b2) and (b2,b0) being shared to X, Y and Z, respectively, in a method similar to the case of data a.
At this time, X computes and records (c0,c1)=(a0+b0,a1+b1), Y computes and records (c1,c2)=(a1+b1,a2+b2), and Z computes and records (c2,c0)=(a2+b2,a0+b0).
(3) Secret Computation of c=a+α (α: a Known Constant)
X computes and records (c0,c1)=(a0+α,a1), and Z computes and records (c2,c0)=(a2,a0+α). Y does not perform processing.
(4) Secret Computation of c=a*α
X computes and records (c0,c1)=(a0*α,a1*α), Y computes and records (c1,c2)=(a1*α,a2*α), and Z computes and records (c2,c0)=(a2*α,a0*α).
(5) Secret Computation of c=a*b (A Multiplication Without Detection of Illegality)
First, X generates random numbers r1, r2 and c0, computes c1=(a0+a1)(b0+b1)−r1−r2−c0, and transmits (r1,c1) and (r2,c0) to Y and Z, respectively.
Next, Y computes y=a1*b2+b1*a2+r1 and transmits y to Z. Further, Z computes z=a2*b0+b0*a2+r2 and transmits z to Y.
Next, each of Y and Z computes c2=y+z+a2*b2.
Then, X records (c0,c1), Y records (c1,c2), and Z records (c2,c0).
(6) Secret Computation of c=a*b (A Multiplication with Detection of Illegality)
After the multiplication of c=a*b is performed by the method of (5) above, the following process is performed for each of X, Y and Z. In the following process, P means each of X, Y and Z. If P is X, P− and P+ means Z and Y, respectively. If P is Y, P− and P+ means X and Z, respectively. If P is Z, P− and P+ means Y and X, respectively.
First, only P− and P+ generate and share a random number r, and P− and P+ distribute r*a0, r*a1 and r*a2 to the respective parties as secret values of r*a. Next, c′=(r*a)*b is computed by the method of (5) above. Then, it is checked whether r*c−c′ is 0 or not, illegality is detected if r*c−c′ is not 0.